package 算法.leetcode;

/**
 * @author:谢君臣
 * @Date:2021/5/16-10:07
 * @version:1.0
 * @function: 给你一个字符串 s，找到 s 中最长的回文子串。
 */
public class lc5 {
    public String longestPalindromeA1(String s){
        if (s.length()<2) {
            return s;
        }
        int start = 0,lenth = 0;
        char[]chars = s.toCharArray();
        int[][] dp = new int[s.length()][s.length()];
//        for (int i = 0; i < dp.length; i++) {
//            dp[i][i] = 1;
//        }
        for (int j = 1; j < dp.length; j++) {
            for (int i = 0; i < j; i++) {
                if (chars[i]!=chars[j]){
                    dp[i][j] = 0;
                }else{
                    if (j-i<3)
                        dp[i][j] = 1;
                    else
                        dp[i][j] = dp[i+1][j-1];
                }
                if (dp[i][j] == 1 && j-i+1>lenth){
                    lenth = j-i+1;
                    start = i;
                }
            }
        }
        return s.substring(start,start+lenth);
    }

    public String longestPalindrome(String s) {
        //边界条件判断
        if (s.length() < 2)
            return s;
        //start表示最长回文串开始的位置，
        //maxLen表示最长回文串的长度
        int start = 0, maxLen = 0;
        int length = s.length();
        for (int i = 0; i < length; ) {
            //如果剩余子串长度小于目前查找到的最长回文子串的长度，直接终止循环
            // （因为即使他是回文子串，也不是最长的，所以直接终止循环，不再判断）
            if (length - i <= maxLen / 2)
                break;
            int left = i, right = i;
            while (right < length - 1 && s.charAt(right + 1) == s.charAt(right))
                ++right; //过滤掉重复的
            //下次在判断的时候从重复的下一个字符开始判断
            i = right + 1;
            //然后往两边判断，找出回文子串的长度
            while (right < length - 1 && left > 0 && s.charAt(right + 1) == s.charAt(left - 1)) {
                ++right;
                --left;
            }
            //保留最长的
            if (right - left + 1 > maxLen) {
                start = left;
                maxLen = right - left + 1;
            }
        }
        //截取回文子串
        return s.substring(start, start + maxLen);
    }
}
